package Data_Structure.Tree;

/**
 * @className: Test1
 * @author: 芃
 * @description: 二叉树
 * @date: 2023/8/17 18:27
 */
public class Test1 {
    //※树相关概念:
    //节点的度：一个节点含有子树的个数
    //树的度：所有节点度的最大值即为树的度
    //叶子节点或终端节点：无子树-》度为0
    //双亲节点或父节点：子节点的父节点
    //孩子节点或子节点
    //根节点：无父节点的节点
    //节点的层次：从根开始定义起，根为第一层，跟的子节点为第二层
    //树的高度：最大层次
    //树的深度：最大深度是树的高度
    //二叉树的每个节点最多有两个子节点（有序树）
    //满二叉树：如果每层的节点数都达到了最大值，则这棵树就是满二叉树 -》2^k-1
    //完全二叉树：每一层都是从左往右依次存放的
    //
    //※二叉树的性质
    //1、根节点的层数为1，则第k层上最多有2^(k-1)个节点
    //2、根节点的二叉树的深度为1，则深度为k的二叉树最多有2^k -1个节点（满二叉树）
    //3、对任意二叉树，若叶子节点个数为n0，度为2的非叶子节点个数为n2，则又n0=n2+1
    // 推导：假设一颗二叉树有N个节点，一颗二叉树，要么n0，要么n1，要么n2
    // N = n0 + n1 + n2 （1）
    // 一个有N个节点的树，应该有N-1条边
    // N-1 = n0*0 + n1*1 + n2*2 (2)
    // (1) (2)表达式推出-》
    // -1 = n2 - n0
    // n0 = n2 + 1 成立
    //4、对于n个节点的完全二叉树的深度k为log2（n+1） 向上取整
    //
    public static void main(String[] args) {

    }
}
